Technical Field
This disclosure pertains in general to distributed computing and in particular to using a distributed computing system to propagate labels in a graph.
Background Information
In graph processing, a computing problem is represented by a graph having a set of vertices connected by a set of edges. The graph can be used, for example, to model a real-world condition, and then the graph processing can act on the graph to analyze the modeled condition. For example, the World Wide Web can be represented as a graph where web pages are vertices and links among the pages are edges. In this example, graph processing can analyze the graph to provide information to a search engine process that ranks search results. Similarly, a social network can be represented as a graph, and graph processing can analyze the graph to learn about the relationships in the social network. Graphs can also be used to model transportation routes, paths of disease outbreaks, citation relationships among published works, and similarities among different documents. Additionally, graphs can be used for machine learning techniques that observe patterns in data in order to adjust future behaviors, such as for spam detection.
Modeling real-world conditions such as those mentioned above involves representing a great deal of information within the graph, as well as updating the graph as processing is performed or new information is received. For graphs modeling complex conditions, representing and updating the information requires significant computing resources.